package com.atguigu.single.joseph;

import com.atguigu.single.Node;

/**
 * @ClassName Joseph
 * @DeScription 约瑟夫
 * @Author 剧情再美终是戏
 * @Date 2019/11/26 20:23
 * @Version 1.0
 **/
public class Joseph {

    private Node head = null;

    // 添加数据
    public void add(Node node) {

        // 如果head为空就进行初始化,并形成环形链表
        if (null == head) {
            head = node;
            head.setNext(head);
            return;
        }

        // 找到链表的最后一个节点
        Node tmp = head;
        while (head != tmp.getNext()) {
            tmp = tmp.getNext();
        }

        // 进行添加节点操作
        tmp.setNext(node);
        node.setNext(head); // 将最后一个节点指向头节点，维护环形
    }

    // 显示
    public void show() {

        // 辅助节点
        Node tmp = head;

        do {
            System.out.println(tmp);
            tmp = tmp.getNext();
        } while (null != tmp && head != tmp);
    }

    // 约瑟夫模拟
    public void showJoseph(int total, int begin, int add) {

        // 参数拦截
        if (1 > total || begin > total || add < 1) {
            System.out.println("参数有误");
            return;
        }

        // 初始化队列
        for (int i = 1; i <= total; i++) {
            Node node = new Node(i, "", "");
            add(node);
        }
        // 输出一次完整的队列
        show();

        // 先定位到从谁开始,以及记录上一个节点
        Node before = head;

        // 1、先让before指向最后一个节点
        while (head != before.getNext()) {
            before = before.getNext();
        }

        // 2、定位从谁开始，每数一个，tmp和before都后移一位
        Node tmp = head;
        while (begin > 1) {
            before = before.getNext();
            tmp = tmp.getNext();
            begin--;
        }

        System.out.println("tmp,before---------------");
        System.out.println(tmp);
        System.out.println(before);

        // 3、开始出队
        System.out.println("开始出队");
        while (tmp != before) {
            int num = add; // 记录每次需要数多少个节点
            while (num > 1) {
                before = tmp;
                tmp = tmp.getNext();
                num--;
            }
            // 出队
            System.out.printf("%d出队\n", tmp.getId());
            tmp = tmp.getNext();
            before.setNext(tmp);

            // 出队之后重置num
            num = add;
        }
        // tmp出队
        System.out.printf("%d出队\n", tmp.getId());
    }
}
